\chapter{Merkle Hash Technique}

\section{Merkle Hash technique MHT}
In 1979 Ralph Merkle proposed a signature scheme in which the public key was used to sign many messages. The idea behind the scheme was to calculate the Merkle hash of the root node by a specified technique and this root node was to be used as the public key. The Merkle hash of the root node was to be calculated by bottom up approach. Firstly hash of each leaf node is calculated. For each next level the hashes or each child node is concatenated to produce the Merkle hash of the parent node. This procedure is carried on till the root node is reached. Hypothetically it can be demonstrated as: 
\newline
For any tree T(V, E), if there is any node ‘n’,
\begin{description}[font=\normalfont\itshape\textbullet\space]
\item Let ‘n’ contains m number of child nodes named as p$_{1}$, p$_{2}$, p$_{3}$, . . . . . ., p$_{m}$
  
\item Then its $\mathit{mh}$(n) will be calculated as: $\mathit{mh}$(n) = $\mathcal{H}$(c$_{n}$) ; If ‘n’ is the leaf node

\item else if; ‘n’ is the intermediate node without content : $\mathit{mh}$(n) = $\mathcal{H}$($\mathit{mh}$(p$_{1}$) $\parallel$ $\mathit{mh}$(p$_{2}$) $\parallel$ $\mathit{mh}$(p$_{3}$) $\parallel$. . . . . $\parallel$ $\mathit{mh}$(p$_{m}$))

\item else; ‘n’ is the intermediate node with content : Then either Merkle hashes of all children of ‘n’ with the content of ‘n’ as described $\mathit{mh}$(n) = $\mathcal{H}$(c$_{n}$ $\parallel$ $\mathit{mh}$(p$_{1}$) $\parallel$ $\mathit{mh}$(p$_{2}$) $\parallel$ $\mathit{mh}$(p$_{3}$) $\parallel$. . . . .  $\parallel$ $\mathit{mh}$(p$_{m}$))

\item Or Merkle hashes of all children of ‘n’ concatenated with the hash of content of ‘n’  as shown $\mathit{mh}$(n) = $\mathcal{H}$($\mathcal{H}$(c$_{n}$) $\parallel$ $\mathit{mh}$(p$_{1}$) $\parallel$ $\mathit{mh}$(p$_{2}$) $\parallel$ $\mathit{mh}$(p$_{3}$) $\parallel$. . . . . $\parallel$ $\mathit{mh}$(p$_{m}$))
\end{description}

For simplicity lets take an example of a family tree in fig 3.1 of Kareem. He has 2 sons i.e. Ali and Said. Ali has 2 sons too namely Aun and Joun, and Saif is also preceded by his two daughters namely Dua and Diya. If a tree is used to store their personal information then this tree will be signed as follows:
\begin{description}[font=\normalfont\itshape\textbullet\space]
\item $\mathit{mh}$(Aun) = $\mathcal{H}$(c$_{Aun}$) 
\item $\mathit{mh}$(Joun) = $\mathcal{H}$(c$_{Joun}$) 
\item $\mathit{mh}$(Ali) = $\mathcal{H}$($\mathcal{H}$(c$_{Ali}$) $\parallel$ $\mathit{mh}$(Aun) $\parallel$ $\mathit{mh}$(Joun)) 
\item $\mathit{mh}$(Dua) = $\mathcal{H}$(c$_{Dua}$) 
\item $\mathit{mh}$(Diya) = $\mathcal{H}$(c$_{Diya}$) 
\item $\mathit{mh}$(Saif) = $\mathcal{H}$($\mathcal{H}$(c$_{Saif}$) $\parallel$ $\mathit{mh}$(Dua) $\parallel$ $\mathit{mh}$(Diya)) 
\item $\mathit{mh}$(Kareem) = $\mathcal{H}$($\mathcal{H}$(c$_{Kareem}$) $\parallel$ $\mathit{mh}$(Ali) $\parallel$ $\mathit{mh}$(Saif)) 
\end{description}

MHT serves the purpose in authenticating and verifying the content of the leaf nodes but it fails to preserve the confidentiality of data. Few applications of MHT are simplified payment verification (SPV), block chain pruning and smart pool miners. 


\section{Leakages During Authentication using MHT}
Let T$_{\delta}$ be a shared subtree of the tree T to be shared with $\mathcal{B}$. Let $\mathit{x}$ be a node in T$_{\delta}$, then $\mathcal{B}$ needs the following auxiliary information to authenticate T$_{\delta}$ (refer to figure 3.1 as example) : 
\newline
\begin{enumerate}
	\item The Merkle hash of each sibling of $\mathit{x}$ which is in T but not in T$_{\delta}$. Example, giving away MH of Dua with respect to Diya.
	
	\item The MH of each sibling s of each ancestor of x, such that s ins not in T$_{\delta}$. Example giving away MH of Ali with respect to Diya.
	
	\item The hash content of each ancestor of x. Example, giving away hash of Ali and Kareem with respect to Aun.
	
	\item Structural ordering between $\mathit{x}$ and its those siblings that are not in T$_{\delta}$ and structural ordering between those siblings of $\mathit{x}$ that are not in T$_{\delta}$. Example, giving away ordering between Diya and Dua with respect to Diya and the ordering between Saif and Ali with respect to Diya.
	
	\item The parent-child relationship between a node in T$_{\delta}$ and a node not in T$_{\delta}$. Example, say T$_{\delta}$ comprises Aun, then giving away parent-child relationship between Ali and Aun. The parent-child relationship between the nodes that are not in T$_{\delta}$. Example, say T$_{\delta}$ comprises of Aun, then giving away the parent-child relationship between Ali and Kareem.
	
	\item The fact that a node is the root node of a tree. Example, giving away the fact that Kareem is the root of the tree.
\end{enumerate}

The user then computes the MH of the whole tree using the subtree $T_{\delta}$ and auxiliary information (above info) and verifies the signature of the original tree using this MH.

\section{MHT Vulnerable to Inference Attacks}
Data becomes vulnerable when 3rd parties are involved in the data chain in the form of distributors, publishers. They act as intermediate data users and can cause two basic attacks:
\newline
\begin{enumerate}
	\item Data tempering: Adversaries (or untrusted distributor in this case) try to temper the content, structural order or edge between two or more nodes of the tree over communication channel.
	\item Inference Attacks: User attempts to extract confidential and sensitive information from the signature and integrity verifiers which are sent to him along with the subtree as the user has complete access to the subtree. These attacks are done on MHT as the auxiliary information sent to the user is quite revealing. There can be a number of inference attacks which can be carried out by exploiting this auxiliary information. Some of them are as follows:
	\newline
	\newline
		2.1 (Plain Text, Cipher Text) Inference Attack: User is provided the subtree (known as plain text) and the auxiliary information with contains cipher text of all those nodes and parts of the tree which are not in the subtree but required for the authentication of the subtree. By comparing the nodes of cipher and plain text, he can deduce whether these nodes are same or not. He can access the Merkle Hash of every ancestor of the nodes in the shared tree. Ha can also get a clue about the first parent of any node in the subtree and infer it if has more child nodes other than the nodes shared. He can also find out that whether a given root in the subtree is also the root node of the entire tree. 
		Suppose In our Example, We share a Sub-Family Tree of Saif and his daughter diya, But the user can deduce from this shared information that Saif has one more child i.e. Dua etc.
	\newline
	\newline
		2.2 (Cipher Text, Cipher Text) Inference Attack: All the auxiliary information provided to the user in MHT are also open to several attacks. User can compare the cipher text of two nodes that are not in the shared subtree to understand that these two nodes are same of not. Further, he can presume about the different subtrees in the auxiliary information. By comparing the roots of two nodes, he can easily figure out that whether they are same or not. He can conclude that whether the subtree is same as that of the main tree.   
		In our Example the auxiliary information contains merkle hash of, Ali, Aun, Joun, Dua  and Kareem. He can compare the hashes of Ali and Aun and can deduce that they are not same. By comparing Aun with Ali he can deduce that Ali is the parent node etc
	\newline
	\newline
		2.3 Structural Inference Attack: User can make a judgement of the size of the subtree by comparing the shared subtree and the auxiliary information. He infers the nodes that are in the tree but not in the shared subtree and can figure out the number of node in the tree and in the unshared subtree. There can be a case that data is only present in the leaf nodes, but if this is not the case then the auxiliary information will be non-empty and can give a clue that which nodes are not a part of the shared subtree.
		In our example User can easily infer that there are 5 more nodes other than the shared subtree. He can infer the size of the subtree.
	\newline
	\newline
		2.4 Missing-Siblings Inference Attack: In this attack user tends to find out that if the number of siblings of a node in the shared subtree are the same as that in the provided data. He compares the auxiliary information with the shared subtree to deduce the number of siblings of the node in the shared subtree and also infers if these nodes are to the right or to the left of the shared nodes.
		In the Example given above User can deduce that Saif has another child and that is on the left of Diya. 
	\newline
	\newline
		2.5 Structural Order Inference Attack: User tries to figure out the structural association between a node in the subtree and other nodes that are not in the shared subtree. Also, he intrudes to find the structural association between two nodes in the unshared subtree. 
		According to our example, He will learn that Diya is the right sibling and Saif is the right sibling of some other node. He will also learn that Saif and Ali are siblings where Ali is the left sibling.
	\newline
	\newline
		2.6 Parent-Child Inference Attack: The user tries to infer the parent-child relationship between the nodes which are in the shared and unshared subtrees and also between two nodes which are not in the shared subtree. 
		In Example User will learn that Kareem and Saif are the parents of Diya and Dua. Also he will infer that Kareem has another child that is not identical to Saif. 
\end{enumerate}